package com.chao.stucture.heap;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 构建大根堆或者小根堆
 * @date : 2023/7/7
 */
public class Heapify {

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        buildMaxRootHeap(arr);
        System.out.println("大根堆：" + Arrays.toString(arr));

        int[] arr2 = {7, 2, 9, 1, 3};
        buildMinRootHeap(arr2);
        System.out.println("小根堆：" + Arrays.toString(arr2));
    }

    public static void buildMaxRootHeap(int []arr) {
        int n = arr.length;
        // 从最后一个非叶子结点开始进行堆化
        for (int i = n / 2 - 1; i >= 0; i--) {
            maxHeapify(arr, i);
        }
    }

    public static void buildMinRootHeap(int []arr) {
        int n = arr.length;
        // 从最后一个非叶子结点开始进行堆化
        for (int i = n / 2 - 1; i >= 0; i--) {
            minHeapify(arr, i);
        }
    }

    private static void maxHeapify(int []arr,int i) {
        int size = arr.length;
        // 假设当前节点是最大值
        int maxIndex = i;
        // 获得左子节点索引
        int left = getLeftSonIndex(i);
        // 获得右子节点索引
        int right = getRightSonIndex(i);

        // 左子节点的值比当前节点大
        if (left < size && arr[left] > arr[maxIndex]) {
            maxIndex = left;
        }

        // 右子节点的值比当前节点大
        if (right < size && arr[right] > arr[maxIndex]) {
            maxIndex = right;
        }

        // 最大值的索引发生改变
        if (maxIndex != i) {
            swap(arr,maxIndex,i);
            maxHeapify(arr,maxIndex);
        }
    }

    private static void minHeapify(int []arr,int i) {
        int size = arr.length;
        int left = getLeftSonIndex(i);
        int right = getRightSonIndex(i);
        int minIndex = i;

        if (left < size && arr[left] < arr[minIndex]) {
            minIndex = left;
        }

        if (right < size && arr[right] < arr[minIndex]) {
            minIndex = right;
        }

        if (minIndex != i) {
            swap(arr,minIndex,i);
            minHeapify(arr, minIndex);
        }
    }

    private static int getLeftSonIndex(int i) {
        return 2 * i +1;
    }

    private static int getRightSonIndex(int i) {
        return 2*i + 2;
    }

    private static void swap(int []arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
